package dp.背包问题;

public class Test {
    public static void main(String[] args) {

        // 假设
        int V = 5; // 背包体积
        int n = 3; // 物品个数
        int[] v = {0, 2, 4, 1}; // 物品体积
        int[] w = {0, 10, 5, 4}; // 物品价值

        // 1. 创建 dp 表， dp[i][j]：从前 i 个物品中挑选，总体积不超过 j ，能挑选出的最大价值
        int[][] dp = new int[n+1][V+1];

        // 2. 填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];

                if(j-v[i] >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j-v[i]] + w[i], dp[i-1][j]);
                }
            }
            
        }

        // 3. 返回
        System.out.println(dp[n][V]);

    }
}











